package Leetcode.Dichotomy;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/4/7 12:57
 * @Description:
 * 分割数组的最大值
 * 困难
 * 相关标签
 * 相关企业
 * 给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
 *
 * 设计一个算法使得这 k 个子数组各自和的最大值最小。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [7,2,5,10,8], k = 2
 * 输出：18
 * 解释：
 * 一共有四种方法将 nums 分割为 2 个子数组。
 * 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
 * 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
 * 示例 2：
 *
 * 输入：nums = [1,2,3,4,5], k = 2
 * 输出：9
 * 示例 3：
 *
 * 输入：nums = [1,4,4], k = 3
 * 输出：4
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 1000
 * 0 <= nums[i] <= 106
 * 1 <= k <= min(50, nums.length)
 */

public class splitArray {

    public int splitArray(int[] nums, int m) {
        // 定义一个二维数组f，其中f[i][j]表示将数组前i个元素分割成不超过j个子数组的最大的和。
        int n = nums.length; // 获取数组的长度
        int[][] f = new int[n + 1][m + 1]; // 初始化f数组，大小为n+1行，m+1列
        for (int i = 0; i <= n; i++) {
            // 将f数组的每个元素初始化为Integer.MAX_VALUE，表示一个不可能达到的值
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        int[] sub = new int[n + 1]; // 初始化一个前缀和数组，用于快速计算任意区间和
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i]; // 计算前缀和
        }
        f[0][0] = 0; // 当没有元素和没有分割时，最大和为0
        for (int i = 1; i <= n; i++) { // 遍历数组的所有元素
            for (int j = 1; j <= Math.min(i, m); j++) { // 遍历分割的子数组数量
                for (int k = 0; k < i; k++) { // 遍历所有可能的分割点
                    f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
                    // f[i][j]的值应该是当前分割点k和分割数j-1下，以及当前子数组的前i个元素和不分割的子数组中的最大值
                }
            }
        }
        return f[n][m]; // 返回到达目标状态（即处理完所有元素，分割数达到m）的最大和
    }

    public int splitArray2(int[] nums, int m) {
        // 初始化左右边界，left为数组中的最小值，right为数组所有元素之和
        int left = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            // 更新right为当前元素加上之前的right，即数组所有元素之和
            right += nums[i];
            // 更新left为当前元素的最大值，确保分割后的子数组不会比这个元素小
            if (left < nums[i]) {
                left = nums[i];
            }
        }
        // 使用二分搜索来逼近最小最大值
        while (left < right) {
            // 计算中间值mid，并检查是否可以分割成不超过m个子数组
            int mid = (right - left) / 2 + left;
            if (check(nums, mid, m)) {
                // 如果可以分割，说明可能还有更小的最大值，所以移动右边界
                right = mid;
            } else {
                // 如果不能分割，说明可能需要更大的最大值，所以移动左边界
                left = mid + 1;
            }
        }
        // 返回最终的left，即最小的最大值
        return left;
    }

    public boolean check(int[] nums, int x, int m) {
        // 初始化子数组的和sum和子数组的数量cnt
        int sum = 0;
        int cnt = 1;
        // 遍历数组，累加元素的值到sum
        for (int i = 0; i < nums.length; i++) {
            // 如果当前元素的和加上sum超过了x，则需要新开一个子数组
            // 并更新子数组的数量cnt和当前子数组的和sum
            if (sum + nums[i] > x) {
                cnt++;
                sum = nums[i];
            } else {
                // 否则，将当前元素的值累加到sum
                sum += nums[i];
            }
        }
        // 如果子数组的数量不超过m，则返回true，否则返回false
        return cnt <= m;
    }


}
